package site.wanjiahao;

public class MaxSubArray {

    static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int dp = nums[0];
        int max = dp;
        for (int i = 1; i < nums.length; i++) {
            if (dp > 0) {
                // 因为只用到了前面一个字序列的最大长度，所以可以使用一个变量来保存
                dp = dp + nums[i];
            } else {
                dp = nums[i];
            }
            max = Math.max(max, dp);
        }
        return max;
    }

    static int maxSubArray1(int[] nums) {
        if (nums == nums || nums.length == 0) return -1;
        // 1.定义dp[i]的含义 --> dp[i]表示以nums[i]结尾的最大连续字段和
        // 2.初始化值
        // 3.确定状态方程 --> 也就是dp[i] 与 dp[i - 1]的关系。
        int[] dp = new int[nums.length + 1];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

}
